from typing import *

from math import inf

from bisect import bisect_left


class Solution:

    def minimumMountainRemovals(self, nums: List[int]) -> int:
        n = len(nums)

        def getLISArray(nums):
            # lis是nums中每个位置的最长递增子序列的长度
            lis, stack = [0] * n, []
            for i, v in enumerate(nums):
                idx = bisect_left(stack, v, key=lambda a: nums[a])
                if idx == len(stack):
                    stack.append(i)
                else:
                    stack[idx] = i
                lis[i] = idx + 1
            return lis

        l = getLISArray(nums)
        r = getLISArray(nums[::-1])[::-1]
        ans = 0
        for i in range(n):
            if l[i] > 1 and r[i] > 1:
                ans = max(ans, l[i] + r[i] - 1)
        return n - ans


so = Solution()
print(so.minimumMountainRemovals([100, 92, 89, 77, 74, 66, 64, 66, 64]))
# print(so.minimumMountainRemovals([9, 8, 1, 7, 6, 5, 4, 3, 2, 1]))
# print(so.minimumMountainRemovals([2,1,1,5,6,2,3,1]))
